package cn.dapeng.tree.binary;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 * 本题测试链接：https://leetcode.com/problems/encode-n-ary-tree-to-binary-tree
 *
 * 把一个多叉树序列化成二叉树
 * 二叉树也能反序列化成多叉树
 */
public class EncodeNaryTreeToBinaryTree {

    /**
     * 多叉树定义
     */
    public static class Node {
        public int value;
        public List<Node> children;

        public Node(int value) {
            this.value = value;
        }
    }

    /**
     * 给一个多叉树，转成二叉树
     * <p>
     * 第一个子节点序列化成父节点的左子树节点，其余子节点序列化成它的右节点
     *
     * @param node
     * @return
     */
    public static TreeNode en(Node node) {
        if (node == null) {
            return null;
        }

        TreeNode head = new TreeNode(node.value);
        head.left = en(node.children);
        return head;
    }

    /**
     * 把多叉树的每一个节点的子节点序列化成一个树
     *
     * @param children
     * @return
     */
    public static TreeNode en(List<Node> children) {
        if (children == null || children.isEmpty()) {
            return null;
        }
        TreeNode head = null, cur = null;

        for (Node n : children) {
            TreeNode tNode = new TreeNode(n.value);
            if (head == null) {
                head = tNode;
            } else {
                cur.right = tNode;
            }
            cur = tNode;
            cur.left = en(n.children);
        }
        return head;
    }

    /**
     * 反序列化过程
     *
     * @param x
     * @return
     */
    public static Node de(TreeNode x) {
        if (x == null) {
            return null;
        }
        Node head = new Node(x.val);

        head.children = deChildren(x.left);

        return head;
    }

    public static List<Node> deChildren(TreeNode leftNode) {
        if (leftNode == null) {
            return null;
        }

        List<Node> children = new ArrayList<>();
        Node node = new Node(leftNode.val);
        children.add(node);
        node.children = deChildren(leftNode.left);

        TreeNode cur;
        if (leftNode.right != null) {
            cur = leftNode.right;
            while (cur != null) {
                node = new Node(cur.val);
                children.add(node);
                node.children = deChildren(cur.left);
                cur = cur.right;
            }
        }
        return children;
    }


    public static void main(String[] args) {
        Node node = new Node(0);

        List<Node> list = new ArrayList<>();

        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);

        Node n1C1 = new Node(4);
        Node n1C2 = new Node(5);
        Node n1C3 = new Node(6);

        n1C2.children = Arrays.asList(new Node(7), new Node(8));

        List<Node> n1cs = new ArrayList<>();
        n1cs.add(n1C1);
        n1cs.add(n1C2);
        n1cs.add(n1C3);
        n1.children = n1cs;
        list.add(n1);
        list.add(n2);
        list.add(n3);

        node.children = list;

        TreeNode head = en(node);
        System.out.println(head);


        node = de(head);
        System.out.println(node);
    }

}
